package dm_pm;

import java.util.Collections;
import java.util.Comparator;
import java.util.Vector;

/**
 * This class will implement DM-PM.
 * 
 * @author Tom Deering
 * @author Dossay Oryspayev
 * 
 */
public final class DM_PM {
	
	/**
	 * Do not let anyone instantiate this class.
	 */
	private DM_PM() {
	}
	
	/**
	 * This is the exact copy of the pseudo code from Figure 7
	 * of the paper.
	 * 
	 * @param Instance to be split.
	 * @param Vector of non-empty processors.
	 * @param time.
	 * @return RESULT
	 */
	public static RESULT doDM_PM(
			Vector<Instance> V_i, int i, Vector<Processor> V_np, long currentTick) {
		long startTime = currentTick;
		Instance instance = V_i.elementAt(i);
		
		for(int np=0; np<V_np.size(); np++) {
			Processor processor = V_np.elementAt(np);
			long c_req = instance.getComputation();
			double c_sk = 0;
			
			for(Instance pInstance : processor.instanceQueue) {
				double x = 0.0;
				
				if(pInstance.isShared()) {
					x = (double) (pInstance.getDeadline()-pInstance.getComputation())/
							(Math.ceil((double)pInstance.getDeadline()/instance.getPeriod()));
				}
				else {
					x = (double) (pInstance.getDeadline()-R_ik(pInstance, processor))/
							(Math.ceil((double)pInstance.getDeadline()/instance.getPeriod()));
				}
				if(x<c_sk) {
					c_sk = Math.max(0, x);
				}
			}
			
			if(c_sk!=0) {
				Instance newInstance = new Instance(
						(long) c_sk, 
						instance.getDeadline(), 
						instance.getTaskID(),
						(int)startTime);
				newInstance.setShared(true);
				newInstance.setPeriod(instance.getPeriod());
				newInstance.setStartTime(startTime);
								
				sortInstances(V_np.elementAt(np).instanceQueue);
				long min_priority = V_np.elementAt(np).instanceQueue.elementAt(0).getPriority();
				if(min_priority<0) {
					// it means this is a shared task
					newInstance.setPriority(min_priority-1);
				}
				else {
					// it means this is a non shared task
					newInstance.setPriority(-1);
				}
				V_np.elementAt(np).instanceQueue.add(newInstance);
				sortInstances(V_np.elementAt(np).instanceQueue);
				startTime += (long) c_sk;
				c_req -= c_sk;
				
				//if(c_req==0) {
					// We can also remove the Instance from set
					//V_i.removeElementAt(i);
					//return RESULT.SUCCESS;
				//}
				//else 
				if(c_req<=0) {
					//c_sk += c_req;
					//newInstance.setComputation((long) newInstance.getComputation()+c_req);
					V_np.elementAt(np).instanceQueue.elementAt(0).setComputation(
							V_np.elementAt(np).instanceQueue.elementAt(0).getComputation()+
							c_req);
					
					// We can also remove the Instance from set
					//V_i.removeElementAt(i);
					return RESULT.SUCCESS;
				}
				else {
					
					// We cannot remove the Instance from set
					// c_req is still positive. But we have to
					// subtract the instance's computation time.
					// It is reflected on c_req not on object.
					V_i.elementAt(i).setComputation(c_req);			
				}
			}			
		}
		return RESULT.FAILURE;
	}
	
	
	/*
	public boolean completionTest(Task T_i, Vector<Task> taskSet) {
		boolean result = false;
		Vector<Task> tempSet = taskSet;
		tempSet.add(T_i);
		sortTasks(tempSet);
		
		if(schedulabilityTest(tempSet)) {
			result = true;
		}
		else {
			int val = 0;
			for(int i=0; i<tempSet.size(); i++) {
				double t0 = 0.0;
				Task currentTask = tempSet.elementAt(i);
					
				for(int j=i; j>=0; j--) {
					Task tempTask = tempSet.elementAt(j);
					long c = tempTask.getComputationTime();
					t0 += c; 					
				}
				
				double computedW_i = 0.0;
				boolean schedulable = false;
				for(;;) {
					computedW_i = W_i(t0, tempSet);
					
					if(computedW_i == t0 && computedW_i <= currentTask.getDeadline()) {
						schedulable = true;
						break;
					}
					else if (computedW_i > currentTask.getDeadline()){
						schedulable = false;
						break;
					}
				}
				
				if(!schedulable) {
					val = i;
					break;
				}
			}
			
			if(val==tempSet.size()-1) {
				result = true;				
			}			
		}
			
		return result;
	}
	
	public double W_i(double t, Vector<Task> taskSet) {
		double result = 0.0;
		for(int i=0; i<taskSet.size(); i++) {
			Task tempTask = taskSet.elementAt(i);
			long c = tempTask.getComputationTime();
			long d = tempTask.getDeadline();
			double td = (double) t/d;
			double ctd = (double) c*Math.ceil(td);
			result += ctd;
		}
		
		return result;
	}
	
	public boolean schedulabilityTest(Vector<Task> taskSet) {
		boolean result = false;
		int size = taskSet.size();
		double summation = 0.0;
		double upperBound = (double)size*(Math.pow(2, (double)1.0/size)-1); 
		
		for(int i=0; i<size; i++) {
			Task tempTask = taskSet.elementAt(i);
			long c = tempTask.getComputationTime();
			long d = tempTask.getDeadline();
			summation += (double) c/d;
		}
		
		if(summation<=upperBound) {
			result = true;
		}
		
		return result;
	}
	
	*/
	/**
	 * Will sort given set of instances according to deadline in non-decreasing orders.
	 * Which will mean that the ones in front will have higher priorities than
	 * the ones in the end.
	 * 
	 * @param Vector of instances.
	 * @return void.
	 */
	public static void sortInstances(Vector<Instance> toSort) {
		Collections.sort(toSort, new Comparator<Instance>() {
			public int compare(Instance i1, Instance i2) {
				long deadline1 = i1.getPriority();
				long deadline2 = i2.getPriority();
				int result;
				
				if(deadline1 > deadline2) {
					result = 1;
				}
			    else if(deadline1 < deadline2) {
			    	result = -1;			    	
			    }
			    else {
			    	result = 0;
			    }
			    return result;
			}
		});
	}
	
	
	/**
	 * The worst-case response time R_ik of each task I_i
	 * on P_k is computed.
	 * 
	 * @param Instance I_i.
	 * @param Set of tasks assigned to processor Pk.
	 * @return the worst-case response time.
	 */
	public static double R_ik(Instance I_i, Processor Pk) {
		double result = 0.0;
		
		Vector<Instance> intersect = new Vector<Instance>();
		sortInstances(Pk.instanceQueue);
			
		for(Instance instance: Pk.instanceQueue) {
			if(I_i.getPriority()>=instance.getPriority()){
				intersect.add(instance);
			}
		}
			
		for(Instance instance: intersect) {
			result += (double) I_ij(I_i, instance) + I_i.getComputation();
		}
		
		return result;
	}
	
	
	/**
	 * Computing the maximum interference that T_i receives
	 * from T_j within interval of length d_i. T_i is assigned
	 * a lower priority than T_j.
	 * 
	 * @param Task T_i.
	 * @param Task T_j.
	 * @return maximum interference.
	 */
	private static double I_ij(Instance I_i, Instance I_j) {
		double result = 0.0;
		double F = (double) I_i.getDeadline()/I_j.getPeriod();
		F = Math.floor(F);
		
		if(I_i.getDeadline() >= ((double)((double)F*I_j.getPeriod()+I_j.getComputation()))) {
			result = (double)((F+1)*I_j.getComputation());
		}
		else {
			result = (double)(I_i.getDeadline()-(double)(F*(I_j.getPeriod()-I_j.getComputation())));
		}
		return result;
	}
	

}